package com.leetcode.problems122;


/**
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    /**
     * dp[i][0] 不持有股票
     *         = Math.max(dp[i - 1][0],prices[i] + dp[i - 1][1])
     * dp[i][1] 持有股票
     *         = Math.max(dp[i - 1][1],-prices[i] + dp[i-1][0])
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if(prices.length <= 1){
            return 0;
        }
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0],prices[i] + dp[i - 1][1]);
            dp[i][1] = Math.max(dp[i - 1][1],-prices[i] + dp[i - 1][0]);
        }
        return dp[prices.length-1][0];
    }
    public static void main(String[] args) {
        int[] prices = {1,6,4,6,9};
        System.out.println(new Solution().maxProfit(prices));
    }
}
